'''
https://leetcode.cn/problems/max-points-on-a-line/?envType=study-plan-v2&envId=top-interview-150
'''
from typing import List


class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        res = 1
        def get_slope_and_bias(p1, p2):
            if p1[0] == p2[0]:
                return 1, 0     # 垂直，算他没有bias
            elif p1[1] == p2[1]:
                return 0, p1[1]
            slope = (p2[1]-p1[1])/(p2[0]-p1[0])
            bias = p1[1] - slope * p1[0]
            return slope, bias

        for i in range(n):
            p1 = points[i]
            for j in range(i + 1, n):
                p2 = points[j]
                slope, bias = get_slope_and_bias(p1, p2)
                cnt = 2
                for k in range(j + 1, n):
                    p3 = points[k]
                    slope2, bias2 = get_slope_and_bias(p1, p3)
                    if slope2 == slope and bias2 == bias:
                        cnt += 1
                res = max(res, cnt)
        return res


